#ifndef GRAPH_H_
#define GRAPH_H_

#include "SLList.h"
#include "DynArray.h"
#include <string>
using namespace std;
#include <queue>

static bool FindWord = false;
template<typename Type> class Graph
{
public:
	struct Edge
	{
		unsigned int toVertex;
	};

	struct Vertex
	{
		// the data that this vertex is storing
		Type element;

		// the list of edges that connect this vertex to another vertex
		SLList<Edge> edges;

		///////////////////////////////////////////////////////////////////////////
		// Function : addEdge
		// Parameters : toVertex - the index of the vertex we are adjacent to
		///////////////////////////////////////////////////////////////////////////
		void addEdge(const unsigned int& toVertex)
		{
			Edge Temporary;
			Temporary.toVertex = toVertex;
			edges.addHead(Temporary);
		}
		void clearEdges()
		{
			edges.clear();
		}
	};

	unsigned int addVertex(const Type& value);
	Vertex& operator[](const unsigned int& index){return VertexDynArray[index];}
	unsigned int size() const;
	void clear();
	void printBreadthFirst(const unsigned int& startVertex);

	//My Functions
	bool IsAnEdge(int edge, Graph<char> *board, int boardindex);
	bool FindFirstLetter(string* UserInput, Graph<char> *board, int boardindex, int wordindex);
	void RecursiveFind(string* UserInput, Graph<char> *board, int boardindex, int wordindex, DynArray<int> *AlreadyChecked);

private:
	DynArray<Vertex> VertexDynArray;
};




/////////////////////////////////////////////////////////////////////////////
// Function : addVertex
// Parameters : value - the data to store in this vertex
// Return : unsigned int - the index this vertex was added at
/////////////////////////////////////////////////////////////////////////////
template<typename Type>
unsigned int Graph<Type>::addVertex(const Type& value)
{
	Vertex Temporary;
	Temporary.element = value;
	VertexDynArray.append(Temporary);
	return VertexDynArray.size() - 1;
}



/////////////////////////////////////////////////////////////////////////////
// Function : operator[]
// Parameters : index - the index in the graph to access
// Return : Vertex& - the vertex stored at the specified index
/////////////////////////////////////////////////////////////////////////////
// template<typename Type>
// Vertex& Graph<Type>::operator[](const unsigned int& index)
// {
// 	return VertexDynArray[index];
// }

/////////////////////////////////////////////////////////////////////////////
// Function : size
// Return : unsiged int - the number of vertices in the graph
/////////////////////////////////////////////////////////////////////////////
template<typename Type>
unsigned int Graph<Type>::size() const
{
	return VertexDynArray.size();
}

/////////////////////////////////////////////////////////////////////////////
// Function : clear
// Notes : clears the graph and redies it for re-use
/////////////////////////////////////////////////////////////////////////////
template<typename Type>
void Graph<Type>::clear()
{
	VertexDynArray.clear();
}

/////////////////////////////////////////////////////////////////////////////
// Function : printBreadthFirst
// Parameters : startVertex - the vertex to start the traversal at
// Notes : prints contents of the graph in depth order 
//			(from closest to farthest)
/////////////////////////////////////////////////////////////////////////////
template<typename Type>
void Graph<Type>::printBreadthFirst(const unsigned int& startVertex)
{
	int Depth = 0;
	int NextDepth = 0;
	int CurrentDepth = 1;
	queue<Vertex> Temporary;
	DynArray<int> PopCheck;
	PopCheck.reserve(VertexDynArray.size());
	for(unsigned int x = 0; x < PopCheck.capacity(); x++)
	{
		PopCheck.append(0);
	}
	Temporary.push(VertexDynArray[startVertex]);
	PopCheck[startVertex] = true;
	while(!Temporary.empty())
	{
		CurrentDepth --;
		SLLIter<Edge> iter(Temporary.front().edges);

		for(iter.begin(); !iter.end(); ++iter)
		{
			if(PopCheck[iter.current().toVertex] == 0)
			{
				Temporary.push(VertexDynArray[iter.current().toVertex]);
				PopCheck[iter.current().toVertex] = 1;
				NextDepth++;
			}
		}
		//DONT UNDERSTAND HOW TO OUTPUT THE DEPTH
		cout << Temporary.front().element << " : " << Depth << endl;
		Temporary.pop();
		if(CurrentDepth == 0)
		{
			CurrentDepth = NextDepth;
			NextDepth = 0;
			Depth++;
		}
	}
}

template<typename Type>
void Graph<Type>::RecursiveFind(string* UserInput, Graph<char> *board, int boardindex, int wordindex, DynArray<int> *AlreadyChecked)
{
	SLLIter<Edge> iter(board->VertexDynArray[boardindex].edges);	
	for(iter.begin(); !iter.end(); ++iter)
	{
		if(board->VertexDynArray[iter.current().toVertex].element == (*UserInput)[wordindex] && ((*AlreadyChecked)[iter.current().toVertex]) != 1)
		{
			(*AlreadyChecked)[iter.current().toVertex] = 1;
			if((wordindex + 1) == UserInput->size())
			{
				FindWord = true;
				return;
			}
			RecursiveFind(UserInput, board, iter.current().toVertex, wordindex + 1, AlreadyChecked);
		}
	}
}

template<typename Type>
bool Graph<Type>::IsAnEdge(int edge, Graph<char> *board, int boardindex)
{
	bool isEdge = false;
	SLLIter<Edge> iter(board->VertexDynArray[boardindex].edges);	
	for(iter.begin(); !iter.end(); ++iter)
	{
		if(iter.current().toVertex == edge)
		{
			return true;
		}
	}
	return false;
}

template<typename Type>
bool Graph<Type>::FindFirstLetter(string* UserInput, Graph<char> *board, int boardindex, int wordindex)
{
	DynArray<int> AlreadyChecked;

	AlreadyChecked.reserve(16);

	for(unsigned int x = wordindex; x < board->size(); x ++)
	{
		if((*UserInput)[wordindex] == board->VertexDynArray[boardindex].element)
		{
			AlreadyChecked[boardindex] = 1;
			RecursiveFind(UserInput, board, x, wordindex + 1, &AlreadyChecked);
			AlreadyChecked.clear();
			AlreadyChecked.reserve(16);
		}
		++boardindex;
	}
	bool Temp = FindWord;
	FindWord = false;
	return Temp;
}

#endif